package Leetcode.链表;

import Leetcode.ListNode;

/**
 * 链表翻转  画图
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *
 * 这种链表翻转，要记得，断开的时候，要先给记录下来，还有操作完，记得都往前挪
 */
public class L206_链表翻转 {
    public ListNode reverseList(ListNode head) {
        ListNode pre,cur,tmp;
        cur = head;
        pre = null;//这个很重要，不要忘了
        while (cur != null){
            //先临时记录，否则丢失下个节点位置
            tmp = cur.next;
            //把原本往下的，转为往前
            cur.next = pre;
            //一起往前挪，这个不要忘了
            pre = cur;
            cur = tmp;
        }
        //记住要返回pre
        return pre;
    }

    //递归也可以2个参数。。。。
    public ListNode reverseList_rec(ListNode head) {
        return rec(null, head);
    }
    public ListNode rec(ListNode pre, ListNode cur){
        if(cur == null){
            return pre;//到头了
        }
        //记录next，避免丢失
        ListNode next = cur.next;
        cur.next = pre;//当前两个节点交换
        //返回下一个节点，因为最后翻转的投在最后面
        return rec(cur, next);
    }


    /**
     * 递归解法， 递归的解法，记得要考虑出口
     * 另外，递归是 自顶向下，从最后一个往下的，考虑的细节不一样
     * 递归就是假设调用到下面的节点了
     */
    public ListNode revlist_rec(ListNode head){
        //先处理终止的情况
        if(head == null || head.next == null){
            return head;
        }
        //拿到下个节点
        ListNode cur = revlist_rec(head.next);
        //如果链表是 1->2->3->4->5，假设head 是 4， cur 是 5，下下个就是空了
        //所以head.next.next 就是5->4，给指回来
        head.next.next = head;
        head.next = null;//断开跟下游的链接，不然会进入循环
        return cur;
    }

}
